翻訳と辞書 Words near each other ・ Leverhulme Memorial ・ Leverhulme Park ・ Leverhulme Trust ・ Leverian collection ・ Leverich Park ・ Levering Act ・ Levering Hall ・ Levering Mission ・ Levenmouth rail link ・ Levenov Point ・ Levens ・ Levens Hall ・ Levens, Cumbria ・ Levensau ・ Levensau High Bridge ・ Levenshtein automaton ・ Levenshtein coding ・ Levenshtein distance ・ Levenshulme ・ Levenshulme High School ・ Levenshulme railway station ・ Levenshulme South railway station ・ Levenson ・ Levenson Self-Report Psychopathy Scale ・ Levenspiel plot ・ Levenstein ・ Levent ・ Levent (Istanbul Metro) ・ Levent (name) ・ Levent Ayçiçek Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Levenshtein automaton ： ウィキペディア英語版 Levenshtein automaton In computer science, a Levenshtein automaton for a string ''w'' and a number ''n'' is a finite state automaton that can recognize the set of all strings whose Levenshtein distance from ''w'' is at most ''n''. That is, a string ''x'' is in the formal language recognized by the Levenshtein automaton if and only if ''x'' can be transformed into ''w'' by at most ''n'' single-character insertions, deletions, and substitutions. ==Applications== Levenshtein automata may be used for spelling correction, by finding words in a given dictionary that are close to a misspelled word. In this application, once a word is identified as being misspelled, its Levenshtein automaton may be constructed, and then applied to all of the words in the dictionary to determine which ones are close to the misspelled word. If the dictionary is stored in compressed form as a trie, the time for this algorithm (after the automaton has been constructed) is proportional to the number of nodes in the trie, significantly faster than using dynamic programming to compute the Levenshtein distance separately for each dictionary word.〔 It is also possible to find words in a regular language, rather than a finite dictionary, that are close to a given target word, by computing the Levenshtein automaton for the word, and then using a Cartesian product construction to combine it with an automaton for the regular language, giving an automaton for the intersection language. Alternatively, rather than using the product construction, both the Levenshtein automaton and the automaton for the given regular language may be traversed simultaneously using a backtracking algorithm.〔 However, the backtracking algorithm may give exponential runtime. Certain Canadian Universities have conducted further study through the application of this automaton for advance backspace spell corrections in mobile environments. The construction of serialized automaton however can take a while to initialize due to the limited CPU performance in a mobile device typically taking 5-6 seconds on a modern ARM architecture processor which is noticeable to the end user. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Levenshtein automaton」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.